package com.gorkr;

import java.util.Arrays;

import org.junit.Test;


/**
 * @author 张心宇 <zhangxinyu20@kuaishou.com>
 * Created on 2022-12-16
 */
public class M31NextPermutation {

    public void nextPermutation(int[] nums) {
        if (nums.length<=1){
            return;
        }

        int end = nums.length - 1;

        int i = end - 1, j = end;
        while (i >=0 && nums[i] >= nums[j] ){
            i--;
            j--;
        }
        if(i>=0){
            // 交换中 更小的数
            int low = nums[i];
            // 寻找大于low的最小high
            j = end;
            while (j >=0 && nums[j]<= low){
                j--;
            }

            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }


        // 从low换处逆序
        for (i++, j = end; i<j; j--,i++){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }

    }

    @Test
    public void test(){

        int[] nums = {1,2};
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }


}
